9.8 KB · ⇊ 3 parts · ⤓ Micron 9.8 KB · ⤓ HTML 44.4 KB

top

Die Robinson-Arithmetik (auch: Q) ist ein endlich axiomatisiertes Fragment der Peano-Arithmetik, eines Axiomensystems der Arithmetik, also der natürlichen Zahlen, innerhalb der Prädikatenlogik erster Stufe. Sie wurde 1950 von Raphael Robinson eingeführt und entspricht im Wesentlichen der Peano-Arithmetik ohne das Axiomenschema der Induktion. Die Bedeutung der Robinson-Arithmetik rührt daher, dass sie endlich axiomatisierbar, aber nicht rekursiv vervollständigbar ist und sogar wesentlich unentscheidbar ist. Dies bedeutet, dass es keine konsistente entscheidbare Erweiterung der Robinson-Arithmetik gibt. Es gibt damit insbesondere auch keine vollständige rekursiv aufzählbare Erweiterung, da diese bereits rekursiv (entscheidbar) wäre.cite-ref-1[1]

• Axiome

• Bedeutsamkeit für die Mathematische Logik

• Literatur

• Einzelnachweise

Die Robinson-Arithmetik ist formuliert in der Prädikatenlogik erster Stufe mit Gleichheit, repräsentiert durch das Prädikat = {\displaystyle =} . Ihre Sprache hat die Konstante 0 {\displaystyle \mathbf {0} } (genannt Null), die Nachfolgerfunktion S {\displaystyle S} (für successor: Nachfolger), welche intuitiv zu einer gegebenen Zahl 1 addiert, sowie die Funktionen + {\displaystyle +} für Addition und × × {\displaystyle \times } für Multiplikation. Sie hat folgende Axiome, die elementare Eigenschaften der natürlichen Zahlen und der arithmetischen Operationen formalisieren:cite-ref-2[2]

• Null hat keinen Vorgänger: S x ≠ 0 {\displaystyle Sx\not =\mathbf {0} }

• Verschiedene Zahlen haben verschiedene Nachfolger: ( S x = S y ) → → x = y {\displaystyle (Sx=Sy)\rightarrow x=y}

• Jede Zahl ist gleich Null oder hat einen Vorgänger: y = 0 ∨ ∨ ∃ ∃ x ( S x = y ) {\displaystyle y=\mathbf {0} \vee \exists x(Sx=y)}

• Rekursive Definition von Addition und Multiplikation:

• x + 0 = x {\displaystyle x+\mathbf {0} =x}

• x + S y = S ( x + y ) {\displaystyle x+Sy=S(x+y)}

• x × × 0 = 0 {\displaystyle x\times \mathbf {0} =\mathbf {0} }

• x × × S y = ( x × × y ) + x {\displaystyle x\times Sy=(x\times y)+x}

Die Robinson-Arithmetik spielt insbesondere beim Beweis des ersten Gödelschen Unvollständigkeitssatzes eine Rolle, da sich innerhalb von Q und ebenso in konsistenten axiomatischen Erweiterungen von Q die Beziehung „… ist ein Beweis der Formel …“ repräsentieren lässt.cite-ref-3[3]

Dabei bedeutet Repräsentierbarkeit eines Prädikats P {\displaystyle P} , dass es eine Formel α α = α α ( x 1 , … … , x n ) {\displaystyle \alpha =\alpha (x_{1},\ldots ,x_{n})} gibt, so dass für alle natürlichen Zahlen a 1 , … … , a n {\displaystyle a_{1},\ldots ,a_{n}} gilt:

(+) falls P ( a 1 , … … , a n ) {\displaystyle P(a_{1},\ldots ,a_{n})} der Fall ist, dann ist die Aussage α α ( a 1 _ _ , … … , a n _ _ ) {\displaystyle \alpha ({\underline {a_{1}}},\ldots ,{\underline {a_{n}}})} in Q beweisbar,

(-) falls P ( a 1 , … … , a n ) {\displaystyle P(a_{1},\ldots ,a_{n})} nicht zutrifft, dann ist die Aussage ¬ ¬ α α ( a 1 _ _ , … … , a n _ _ ) {\displaystyle \neg \alpha ({\underline {a_{1}}},\ldots ,{\underline {a_{n}}})} in Q beweisbar.cite-ref-4[4]

Der Term a _ _ {\displaystyle {\underline {a}}} ist dabei wie folgt definiert:

0 _ _ = 0 {\displaystyle {\underline {0}}=\mathbf {0} } ,

n + 1 _ _ = S n _ _ {\displaystyle {\underline {n+1}}=S{\underline {n}}} .cite-ref-5[5]

Das zugehörige Beweisbarkeitsprädikat „… ist beweisbar“ (d. h. „es gibt ein b {\displaystyle b} , das ein Beweis der Formel … ist“) ist nicht in Q repräsentierbar, weil keine seiner negativen Instanzen („die Formel … ist nicht beweisbar“) in Q beweisbar ist. Es kann jedoch durch eine Σ1-Formel ausgedrückt werden, und daher folgt aus der Σ1-Vollständigkeit von Q,cite-ref-6[6] dass jede seiner positiven Instanzen beweisbar ist. Unter Σ1-Vollständigkeit ist hier zu verstehen, dass jede Σ1-Aussage (der Sprache von Q), die für die natürlichen Zahlen gilt, auch in Q beweisbar ist.cite-ref-7[7]

Q ist bereits in relativ schwachen Subtheorien von ZFC interpretierbar, etwa im sogenannten Tarski-Fragment TF,cite-ref-8[8] das nur aus folgenden drei Axiomen besteht: dem Extensionalitätsaxiom (auch Axiom der Bestimmtheit), dem Leermengenaxiom (auch Nullmengenaxiom: die leere Menge existiert) und dem Axiom, welches für zwei Mengen x {\displaystyle x} , y {\displaystyle y} die Existenz der adjungierten Menge x ∪ ∪ { y } {\displaystyle x\cup \{y\}} fordert.

• A. Bezboruah, John C. Shepherdson: Gödel’s Second Incompleteness Theorem for Q. In: Journal of Symbolic Logic. Band 41, Nr. 2, 1976, S. 503–512, JSTOR:2272251.

• George S. Boolos, John P. Burgess, Richard C. Jeffrey: Computability and Logic. 5. Auflage. Cambridge University Press, Cambridge etc. 2007.

• Petr Hájek, Pavel Pudlák: Metamathematics of first-order arithmetic. 2. Auflage. Springer-Verlag, 1998.

• Raphael Robinson: An Essentially Undecidable Axiom System. In: Proceedings of the International Congress of Mathematics. 1950, S. 729–730.

• Alfred Tarski, Andrzej Mostowski, Raphael Robinson: Undecidable theories. North Holland, 1953.

• Hans Hermes: Einführung in die mathematische Logik. 2. Auflage. B. G. Teubner Stuttgart, 1969.

• Wolfgang Rautenberg: Einführung in die Mathematische Logik. 3. Auflage. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2, doi:10.1007/978-3-8348-9530-1.

• Donald Monk: Mathematical Logic (= Graduate Texts in Mathematics. Band 37). Springer, New York 1976, ISBN 0-387-90170-1.

cite-note-11. ↑ Rautenberg (2008), Satz 6.4.4, S. 191

cite-note-22. ↑ George Boolos, John P. Burgess, Richard Jeffrey: Computability and Logic. 4. Auflage. Cambridge University Press, 2002, ISBN 0-521-70146-5, S. 56.

cite-note-33. ↑ W. Rautenberg (2008), S. 186.

cite-note-44. ↑ W. Rautenberg (2008), S. 184.

cite-note-55. ↑ W. Rautenberg (2008), S. 83.

cite-note-66. ↑ W. Rautenberg (2008), S. 190.

cite-note-77. ↑ W. Rautenberg (2008), S. 186.

cite-note-88. ↑ D. Monk (1976), S. 283–290.